package Atop100.listNode;

import java.util.HashMap;
import java.util.LinkedList;

//https://blog.csdn.net/dong_W_/article/details/105337416
public class LFUcacheDemo {

        private int capacity;
        private int minFred;

        private HashMap<Integer,Node> cache;
        private HashMap<Integer, LinkedList<Node>> fredMap;

        public LFUcacheDemo(int capacity) {
            this.capacity=capacity;
            cache = new HashMap<>(capacity);
            fredMap = new HashMap<>();
            minFred=0;
        }

        public int get(int key) {
            if(capacity==0){
                return -1;
            }
            Node node = cache.get(key);
            if(node==null){
                return -1;
            }
            fredIncrease(node);
            return node.getValue();
        }

        private void fredIncrease(Node node) {
            int fred = node.getFred();
            LinkedList<Node> fredList = fredMap.get(fred);
            fredList.remove(node);
            if(node.getFred()==minFred&&fredList.isEmpty()){
                minFred++;
            }
            fredList=fredMap.get(fred+1);
            if(fredList==null||fredList.size()==0){
                fredList=new LinkedList<>();
                fredMap.put(fred+1,fredList);
            }
            fredList.addFirst(node);
            node.fredInc();
        }

        public void put(int key, int value) {
            if(capacity==0){
                return;
            }
            Node node = cache.get(key);
            if (node != null) {
                node.setValue(value);
                fredIncrease(node);
                return;
            }
            node = new Node(key, value);

            if (cache.size() == capacity) {
                LinkedList<Node> fredList = fredMap.get(minFred);
                Node last = fredList.removeLast();
                cache.remove(last.getKey(),last);
            }
            cache.put(key, node);
            LinkedList<Node> fredList = fredMap.get(0);
            if (fredList == null) {
                fredList = new LinkedList<>();
                fredMap.put(0, fredList);
            }
            fredList.addFirst(node);
            minFred = 0;
            return;

        }

        public static void main(String[] args) {
            LFUcacheDemo cache =new LFUcacheDemo(3);
            cache.put(3, 1);
            cache.put(2, 1);
            System.out.println(cache.cache.keySet());
            cache.put(2, 2);
            System.out.println(cache.cache.keySet());

            cache.put(4, 4);
            System.out.println(cache.cache.keySet());

            int res1 = cache.get(2);
            System.out.println(res1);

            int res2 = cache.get(3);
            System.out.println(res2);

            int res3 = cache.get(2);
            System.out.println(res3);

            int res4 = cache.get(1);
            System.out.println(res4);

            cache.put(5, 5);

            int res5 = cache.get(1);
            System.out.println(res5);

            int res6 = cache.get(2);
            System.out.println(res6);

            int res7 = cache.get(3);
            System.out.println(res7);

            int res8 = cache.get(4);
            System.out.println(res8);

            int res9 = cache.get(5);
            System.out.println(res9);
        }
    }

    class Node{
        private int key;
        private int value;
        private int fred = 0;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public void setValue(int value) {
            this.value = value;
        }

        public int getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }

        public int getFred() {
            return fred;
        }

        public void fredInc(){
            fred++;
        }
    }


